/*
要求：求两个数组最大子数组点积和，两子数组等长，点积和即相同位置元素乘积和
策略：动态规划，dp[i][j]表示nums1[0...i]和nums2[0...j]最大点积和
      递推关系式考虑四种情况：Math.max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]*nums1[i]*nums2[j],nums1[i]*nums2[j])
 */
public class MaxDotProduct {
}
class MaxDotProductSolution{
    int maxDotProduct(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        int[][] dp = new int[n1][n2];
        dp[0][0] = nums1[0]*nums2[0];
        for(int i=1;i<n2;i++)
            dp[0][i] = Math.max(dp[0][i-1],nums1[0]*nums2[i]);
        for(int i=1;i<n1;i++)
            dp[i][0] = Math.max(dp[i-1][0],nums1[i]*nums2[0]);
        int max = Integer.MIN_VALUE;
        for(int i=1;i<n1;i++){
            for(int j=1;j<n2;j++){
                dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                dp[i][j] = Math.max(dp[i][j],Math.max(dp[i-1][j-1],0)+nums1[i]*nums2[j]);
            }
        }
        return dp[n1-1][n2-1];
    }
}
